0977. 有序数组的平方【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法
• 3. 🎯 s.2 - 双指针（O(n)）

1. 📝 题目描述

• leetcode

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

---

示例 1：

输入：nums = [-4, -1, 0, 3, 10]
输出：[0, 1, 9, 16, 100]

解释：
平方后，数组变为 [16, 1, 0, 9, 100]
排序后，数组变为 [0, 1, 9, 16, 100]

---

示例 2：

输入：nums = [-7, -3, 2, 3, 11]
输出：[4, 9, 9, 49, 121]

---

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 已按非递减顺序排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  return nums.map((item) => item * item).sort((a, b) => a - b)
}

• 时间复杂度：$O(n\log n)$
• 空间复杂度：$O(n)$

算法思路：

• 平方 + 排序（直观解）
• 先将每个元素平方，再对平方数组进行升序排序，得到非递减序列

3. 🎯 s.2 - 双指针（O(n)）

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function (nums) {
  const n = nums.length
  const res = new Array(n)
  let l = 0
  let r = n - 1
  let k = n - 1
  while (l <= r) {
    const lsq = nums[l] * nums[l]
    const rsq = nums[r] * nums[r]
    if (lsq > rsq) {
      res[k--] = lsq
      l++
    } else {
      res[k--] = rsq
      r--
    }
  }
  return res
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 原数组已按非递减排序，负数的平方可能比正数大
• 使用双指针从两端比较绝对值大的平方，依次从结果数组尾部填入，最终得到非递减的平方数组